package com.zy.heap;


import cn.hutool.core.collection.CollectionUtil;
import com.google.common.base.Joiner;
import com.google.common.collect.Lists;

import java.util.List;

/**
 * @author zhaoyi
 * @date 2021/12/2 2:32 下午
 * <p>
 * 据结构堆和内存模型中的堆内存完全没关系
 * - 是一个完二叉树（用数组存放节省空间,堆不满足二叉树的有序性）
 * - 每个节点必须大于等于[大顶堆]（或者都小于等于[小顶堆]）子树中每个节点
 *
 * <p>
 * ---------A(0)
 * ------/       \
 * ----B(1)      C(2)
 * ----/  \     /
 * D(3)  E(4) F(5)
 * <p>
 * [A,B,C,D,E,F]
 * <p>
 * 数组中下标为 i 的节点的左子节点，就是下标为(i*2 +1) 的节点，
 * 右子节点就是下标为i*2+2的节点，
 * 父节点就是下标为(i-1)/2  的节点。
 */
public class Heap<T extends Comparable<T>> {

    //存放数据
    private final List<T> data;

    //true 小顶堆 false 大顶
    private final boolean min;

    public Heap(int size, boolean isMin) {
        data = Lists.newArrayListWithCapacity(size);
        this.min = isMin;
    }

    /**
     * 删除 从上向下堆化
     * 正常都是从堆顶弹出 随意下标删除无意义
     */
    public T pop() {
        if (CollectionUtil.isEmpty(data)) {
            return null;
        }
        T t = data.get(0);
        int last = data.size() - 1;
        if (last <= 1) {
            data.remove(0);
            return t;
        }
        //把最后一个放头上去向下堆化
        T lt = data.remove(last);
        data.set(0, lt);


        //向下堆化
        int i = 0;
        int maxIndex = data.size() - 1;

        while (true) {
            int l = i * 2 + 1;
            int r = i * 2 + 2;
            if (maxIndex < l) {
                break;
            } else {
                int sw = l;
                T d = data.get(i);
                T ld = data.get(l);
                if (maxIndex >= r) {
                    T rd = data.get(r);
                    if ((min && rd.compareTo(ld) < 0) || (!min && ld.compareTo(rd) < 0)) {
                        sw = r;
                    }
                }
                if ((d.compareTo(data.get(sw)) > 0 && min) || (!min && d.compareTo(data.get(sw)) < 0)) {
                    swap(i, sw);
                    i = sw;
                } else {
                    break;
                }
            }
        }
        return t;
    }


    //插入元素
    //堆化从下往上
    public void put(T t) {
        data.add(t);
        int i = data.size() - 1;
        int p = (i - 1) / 2;
        while (true) {
            if (p < 0) {
                break;
            } else if ((min && data.get(p).compareTo(t) > 0) || (!min && data.get(p).compareTo(t) < 0)) {
                //交换
                swap(i, p);
                i = p;
                p = (i - 1) / 2;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int p) {
        T tmp = data.get(i);
        data.set(i, data.get(p));
        data.set(p, tmp);
    }

    public int getSize(){
        return data.size();
    }

    //查看堆顶元素
    public T topLook(){
        if (data.size() > 0){
            return data.get(0);
        }else {
            return null;
        }
    }


    @Override
    public String toString() {
        return Joiner.on(",").join(data).toString();
    }

    public static void main(String[] args) {
        Heap<String> heap = new Heap<>(16, true);
        heap.put("B");
        heap.put("A");
        heap.put("E");
        heap.put("D");
        heap.put("F");
        heap.put("C");
        System.out.println(heap);

        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
    }


}
